package com.leetcode.array_matrix;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/8/1 22:29
 */
public class Merge_56 {

    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if (len == 0) return new int[0][];
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < len; i++) {
            if (intervals[i][0] > end) {
                list.add(new int[]{start, end});
                // start保证是最小的
                start = intervals[i][0];
            }
            // 不断更新边界最大值
            end = Math.max(end, intervals[i][1]);
        }
        // 遍历到最后暂时不会加入
        list.add(new int[]{start, end});
        return list.toArray(new int[0][]);
    }

    static class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) return new int[0][];

            List<int[]> res = new ArrayList<>();
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

            int i = intervals[0][0], j = intervals[0][1], len = intervals.length;
            for (int k = 1; k < len; k++) {
                int x = intervals[k][0], y = intervals[k][1];
                if (x <= j) {
                    j = Math.max(j, y);
                } else {
                    res.add(new int[]{i, j});
                    i = x;
                    j = y;
                }
            }
            res.add(new int[]{i, j});
            return res.toArray(new int[0][]);
        }
    }

}
